class DrawGraph

	def initialize
		@graph = {}	 # graph = {node => { path1 => distance1, path2 => distance2}, node2 => ...
		@points = Array.new		 
		@INFINITY = 1 << 64
	end
		
	def add_path(s, t, d) 		# s= source, t= target, d= distance
		if (not @graph.has_key?(s))
			@graph[s] = {t => d}		 
		else
			@graph[s][t] = d        
		end

		if (not @points.include?(s))	
			@points << s
		end
		if (not @points.include?(t))
			@points << t
		end	
	end
	
	def dijkstra(s)
		@dist = {}
		@prev = {}
		@points = @points.sort

		@points.each do |i|
			@dist[i] = @INFINITY
			@prev[i] = -1
		end	

		@dist[s] = 0
		q = @points.compact
		while (q.size > 0)
			u = nil;
			q.each do |min|
				if (not u) || (@dist[min] && @dist[min] < @dist[u])
					u = min
				end
			end
			if (@dist[u] == @INFINITY)
				break
			end
			q = q - [u]
			@graph[u].keys.each do |v|
				alt = @dist[u] + @graph[u][v]
				if (alt < @dist[v])
					@dist[v] = alt
					@prev[v]  = u
				end
			end
		end
	end
	
	def print_path(dest)
		if @prev[dest] != -1
			print_path @prev[dest]
		end
		print "#{dest} "
	end
	
	def shortest_path(s)
		dijkstra s

		puts "Plus courts chemins : "
		2.times do |nb|
			@points.each do |i|
				if nb == 0
					print "#{i} "
				else
					print "#{@dist[i]} "
				end
			end
			print "\n"
		end

		@points.each do |dest|
	
			if @dist[dest] != @INFINITY and @dist[dest] > 0
		print_path dest
				puts "#{@dist[dest]}"
			end
		end
	end
end
